-- 八皇后（ eight queen ）问题。
-- 解决八皇后问题就是把八个不同的 queen 放到一个 8 x 8 棋盘上，每个 queen 之间都不能相互攻击。

N = 8 -- 棋盘大小 N x N

-- 检查位置 (n, c) 是否是安全的位置。
function isplaceok(a, n, c)
	for i = 1, n - 1 do -- 遍历已经存在的 queen 进行检查
		if a[i] == c or -- 同一列
		   a[i] - i == c - n or -- 左上到右下的对角斜线
		   a[i] + i == c + n then -- 右上到左下的对角斜线
			return false -- 该位置会被攻击
		end
	end
	return true -- 该位置安全
end

-- 打印棋盘
function printsolution(a)
	for i = 1, N do
		for j = 1, N do
			io.write(a[i] == j and "X" or "-", " ")
		end
		io.write("\n")
	end
	io.write("\n")
end

-- 解决八皇后问题一个有效的条件就是棋盘每一行只能有一个 queen 。
-- 因此用数组 a 存放 8 个数字，每行一个，数组元素表示该行的 queen 处于第几列，
-- 很明显数组元素值处于范围 [1, 8] 。
-- 把 n 到 N 个 queen 添加到数组 a 中。
-- 函数使用 backtracking 找到所有的解决方案。
function addqueen(a, n)
	if n > N then
		printsolution(a) -- 所有 queen 已经被放置完毕
	else
		for c = 1, N do
			if isplaceok(a, n, c) then
				a[n] = c -- 把第 n 个 queen 放在第 c 列
				addqueen(a, n + 1)
			end
		end
	end
end

addqueen({}, 1)
